//
// Created by 英语好难 on 2023/5/19.
//
#include <stdio.h>
#include <stdlib.h>



int seq_search(int array[], int n, int k, int seek_seq[])
{
    //在顺序表array[0..n-1]中查找关键字为k的记录
    for (int i = 0; i < n; ++i) {
        seek_seq[i] = i;
        if (array[i] == k)
        {
            return 0;
        }
    }
    return -1;
}

void r(int low, int high, int k, int array[], int* G, int seek_seq[], int location) {
    //在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
    //无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
    int middle = (low + high) / 2;
    seek_seq[location] = middle;
    location++;
    if (low > high) {
        *G = -1;
        return;
        printf("low>high\n");
    }
    if (low == middle) {
        *G = high;
        return;
        printf("low==middle\n");
    }
    if (k > array[middle]) {
        printf("k>array[middle]\n");
        printf("array[middle]:%d\n", array[middle]);
        printf("---------------\n");
        r(middle + 1, high, k, array, &G, seek_seq, location);
    }
    if (k < array[middle]) {
        printf("k<array[middle]\n");
        printf("array[middle]:%d\n", array[middle]);
        printf("---------------\n");
        r(low, middle - 1, k, array, &G, seek_seq, location);
    }
    if (k == middle) {
        printf("k=array[middle]\n");
        printf("array[middle]:%d\n", array[middle]);
        printf("---------------\n");
        *G = middle;
        return;
    }
    return;
}



int bin_search(int array[], int n, int k, int seek_seq[]) {
    //在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
    //无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
    int* G;
    r(0, n - 1, k, array, &G, seek_seq, 0);
    if (G = -1) {
        return -1;
    }
    else
        return G;

}
int main() {

    int n = 10;
    int array[] = { 0,1,2,3,4,5,6,7,8,9 };
    int seek_seq[10];

    for (int i = 0; i < n; ++i) {
        seek_seq[i] = -1;
    }
    int c = seq_search(array, n, 6, seek_seq);
    printf("%d\n", c);
    for (int i = 0; i < n; ++i) {
        printf("%d,", seek_seq[i]);
    }
    for (int i = 0; i < n; ++i) {
        seek_seq[i] = -1;
    }
    printf("\n");
    int d = bin_search(array, n, 4, seek_seq);
    printf("%d\n", d);
    for (int i = 0; i < n; ++i) {
        printf("%d,", seek_seq[i]);
    }
    return 0;
}

